package org.example.two.sort;

import org.example.two.Example;

public class MerageAmend extends Example {
    private Comparable[] aux;
    @Override
    public void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }

    public void sort(Comparable[] a , int lo , int hi){
        if (lo >= hi ){
            return;
        }
        int mit = lo + (hi - lo )/2;
        if (hi-lo <= 10){
            selection(a,lo,hi);
        }else {
            sort(a,lo,mit);
            sort(a,mit+1,hi);
            merage(a,lo,mit,hi);
        }

    }

    public void merage(Comparable[] a,int lo,int mid ,int hi){
        if (les(a[mid],a[mid+1])){
            return;
        }

        System.arraycopy(a,lo,aux,lo,hi-lo+1);
        int j = lo;
        int k =mid+1;

        for (int i = lo; i <= hi; i++) {
            if (j>mid){
                a[i] = aux[k++];
            }else if (k>hi){
                a[i] = aux[j++];
            }else if(les(aux[k],aux[j])){
                a[i] = aux[k++];
            }else {
                a[i] = aux[j++];
            }
        }

    }

    public void selection(Comparable[] a , int lo ,int hi){

        for (int i = lo; i <= hi ; i++) {
            for (int j = i; j > lo && les(a[j],a[j-1]); j--) {
                exch(a,j,j-1);
            }
        }
    }
}
